#include<iostream>
#include<vector>
#include<string>
#include<cstdlib>
#include<unordered_map>
#include<algorithm>
using namespace std;
vector<int> Available; // 可利用资源向量 
vector<vector<int>> Max; // 最大需求矩阵 
vector<vector<int>> Allocation; // 分配矩阵
vector<vector<int>> Need; // 需求矩阵
vector<vector<int>> tmp;  // 中间变量矩阵，用作实现运算符重载时提升效率 
string safe;				//  安全序列 
unordered_map<int, int> Hash; // 用作排序后建立索引---<进程编号，对应排序后的数组下标>
int flag = 1; // 排序后标记为0，用作后续区分打印安全序列过程
int m = 0, n = 0; 			  // m类资源，n个进程 
// 为了代码的简洁，这里实现运算符重载
inline vector<vector<int>>& operator-(vector<vector<int>>& v1, vector<vector<int>>& v2)
{
	tmp = v1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			tmp[i][j] = v1[i][j] - v2[i][j];
	return tmp;
}
inline void operator-=(vector<int>& v1, vector<int>& v2)
{
	for (int i = 0; i < m; i++) v1[i] -= v2[i];
}
inline void operator+=(vector<int>& v1, vector<int>& v2)
{
	for (int i = 0; i < m; i++) v1[i] += v2[i];
}
bool operator<=(vector<int>& v1, vector<int>& v2)
{
	for (int i = 0; i < m; i++)
		if (v1[i] > v2[i])
			return false;
	return true;
}
ostream& operator<<(ostream& cout, vector<int>& v)
{
	for (int i = 0; i < m; i++) cout << v[i] << " ";
	return cout;
}
void input()
{
	cout << "请输入系统中一共有多少类资源，当前一共有多少个进程" << endl;
	cin >> m >> n;
	// 初始化数据结构，每行都多开一个空间，最后一个空间表示是进程序号(进程从1开始编号) 
	Available.resize(m), Max.resize(n, vector<int>(m + 1));
	Allocation = Need = Max;
	cout << "请依次输入当前系统中每类资源可用的数目" << endl;
	for (int i = 0; i < m; i++) cin >> Available[i];
	cout << "请依次输入每个进程对每类资源的最大需求" << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cin >> Max[i][j];
		Max[i][m] = i + 1;
	}
	cout << "请依次输入当前系统中每类资源已分配给每个进程的数目" << endl;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cin >> Allocation[i][j];
		Allocation[i][m] = i + 1;
	}
	Need = Max - Allocation;
}
// 展示结果的打印
void display1()
{
	int flag = 1;
	cout << "进程|资源情况       Max          Allocation          Need          Available" << endl;
	// 以Need矩阵作标记来打印资源情况
	for (int i = 0; i < n; i++)
	{
		int index = Need[i][m];
		cout << index <<"                 "; // 进程编号
		// 这里是打印Need[i]，是以Need矩阵为中心讨论
		cout << Max[index - 1] <<"            " << Allocation[index - 1] 
			<< "            " << Need[i] << "          "; 
		if (flag == 1)
		{
			cout << Available;
			flag = 0;
		}
		cout << endl;
	}
}
// 展示安全序列过程的打印---排序方法
void display2()
{
	vector<int> Work = Available; // 工作向量 
	cout << "进程|资源情况       Work          Need          Allocation          Work+Allocation" << endl;
	if (flag == 1) // 普通方案
	{
		for (int i = 0; i < safe.size(); i++)
		{
			int index = safe[i] - '0'; // 先计算进程编号
			cout << index << "                 " << Work << "            ";
			cout << Need[index - 1] << "            " << Allocation[index - 1] << "            ";
			Work += Allocation[index - 1];
			cout << Work << endl;
		}
	}
	else // 排序方案
	{
		for (int i = 0; i < safe.size(); i++)
		{
			int index = safe[i] - '0'; // 先计算进程编号
			cout << index << "                 " << Work << "            ";
			cout << Need[Hash[index]] << "            " << Allocation[index - 1] << "            ";
			Work += Allocation[index - 1];
			cout << Work << endl;
		}
	}
}
// 法一：
bool CheckSafe()
{
	vector<int> Work = Available; // 工作向量 
	vector<bool> check(n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (check[j] == false)
			{
				if (Need[j] <= Work)
				{
					Work += Allocation[j];
					check[j] = true;
					safe += (j + 1) + '0';
					// 所有进程组成安全序列就直接返回
					if (safe.size() == n)
						return true;
				}
			}
		}
	}
	// 可能循环出来没有找到所有进程组成安全序列
	if (safe.size() == n)
		return true;
	else return false;
}
// 法二：排序
//bool CheckSafe()
//{
//	flag = 0;
//	vector<int> Work = Available; // 工作向量 
//	vector<bool> check(n);
//	// 小贪心---按需求资源数排序,这里重写比较方法
//	// 排序规则是，以Need矩阵中的第一个资源数为准，找第一个资源数最小的数组按升序排在最前面
//	// 如果存在两个或多个数组，其第一个资源数相等，则再比较第二个资源数的大小，依旧小的排前面，以此类推
//	// 注意数组最后一个位置是进程编号，不参与排序
//	sort(Need.begin(),Need.end(),[&](const vector<int>&v1,const vector<int>& v2)
//	{
//			for (int i = 0; i < v1.size() - 1; i++)
//			{
//				if (v1[i] < v2[i]) return true;
//				else if (v1[i] == v2[i]) continue;
//				else return false;
//			}
//			return true;
//	});
//	// 哈希映射一下，方便后续打印安全序列的过程---<进程编号，对应排序后的数组下标>
//	for (int i = 0; i < n; i++)
//		Hash[Need[i][m]] = i;
//	// 排序后，必然是按第一个资源数最小的由升序排在前头
//	// 别被两层n重循环骗到，实际上这里的复杂度没有N^2
//	// 因为有cnt变量和check检测数组的存在，当一次遍历后cnt还是原值
//	// 根据排序的特性，即可推断当前是不存在安全序列的
//	cout << "排序后，资源分配图如下所示（进程从1开始编号）" << endl;
//	display1();
//	for (int i = 0; i < n; i++)
//	{
//		int cnt = safe.size();
//		for (int j = 0; j < n; j++)
//		{
//			if (Need[j] <= Work)
//			{
//				if (check[j] == false)
//				{
//					Work += Allocation[Need[j][m] - 1];
//					check[j] = true;
//					safe += (Need[j][m]) + '0';
//				}
//			}
//		}
//		// 所有进程构成安全序列就提前返回
//		if (safe.size() == n) return true;
//		// 一个遍历下来依旧没有让安全序列增加，则说明没有进程符合安全序列的条件了，直接返回
//		else if(cnt == safe.size()) return false;
//	}
//	// 所有进程能构成安全序列就返回true
//	 return false;
//}
// 提供一种求所有安全序列的方法---回溯
vector<string> ret;
vector<bool> Check;
string path;
void dfs(vector<int>& Work, int pos)
{
	if (path.size() == n)
	{
		ret.push_back(path);
		return;
	}
	for (int i = pos; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (Check[j] == false)
			{
				if (Need[j] <= Work)
				{
					Work += Allocation[j];
					Check[j] = true;
					path += (j + 1) + '0';
					dfs(Work, i + 1);
					Work -= Allocation[j];
					Check[j] = false;
					path.pop_back();
				}
			}
		}
	}
}
void AllSafe()
{
	vector<int> Work = Available; // 工作向量 
	Check.resize(n);
	dfs(Work,0);
	for (auto& str : ret)
	{
		for (auto& ch : str)
			cout << ch << "->";
		cout << endl;
	}
}
void BankesAlgorithm()
{
	input(); // 输入数据	
	system("cls");
	cout << "当前资源分配图如下所示（进程从1开始编号）" << endl;
	display1();
	vector<int> Request(m + 1); // 多开一个空间，最后一个空间表示是进程序号 
	cout << "请输入当前是哪个进程需要申请资源" << endl; cin >> Request[m];
	cout << "请输入该进程当前每类资源申请的数目" << endl;
	for (int i = 0; i < m; i++) cin >> Request[i];
	bool flag1 = Request <= Need[Request[m] - 1];
	if (flag1 == 0) // 出错就直接退出 
	{
		cout << "进程 " << Request[m] << " 其申请的资源已超过它所宣布的最大值！这是错误的！" << endl;
		exit(1);
	}
	bool flag2 = Request <= Available;
	if (flag2 == 0) // 可能当前剩余资源数不能满足进程申请数 
	{
		cout << "当前尚无足够资源，进程 " << Request[m] << " 需等待！" << endl;
		exit(1);
	}
	// 都满足了，先试着进行资源分配，然后执行安全性算法检测 
	Available -= Request;
	Allocation[Request[m] - 1] += Request;
	Need[Request[m] - 1] -= Request;
	cout << "先预进行资源分配，此时预分配后的资源分配图如下所示（进程从1开始编号）" << endl;
	display1();
	cout << "其中所有的安全序列为：" << endl;
	AllSafe();
	if (CheckSafe())
	{
		cout << "进程 " << Request[m] << " 存在安全序列，可直接分配资源，安全序列为：" << endl;
		for (int i = 0; i < safe.size(); i++)
			cout << safe[i] << "->";
		cout << endl << "其中安全序列的过程如下所示：" << endl;
		display2();
	}
	else
	{
		cout << "不存在安全序列，这样分配可能会引发死锁！" << endl;
		Available += Request;
		Allocation[Request[m]] -= Request;
		Need[Request[m]] += Request;
		exit(1);
	}
}
int main()
{
	BankesAlgorithm();
	return 0;
}